import java.util.Arrays;
import java.util.Random;
import java.util.Random;

public class MyBigInteger {
    public static final int DEFAULT_PRIME_CERTAINTY = 100;
    public static final int[] SMALL_PRIMES = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
    public static final MyBigInteger ZERO = new MyBigInteger("0");
    public static final MyBigInteger ONE = new MyBigInteger("1");
    public static final MyBigInteger TWO = new MyBigInteger("2");
    public static final MyBigInteger THREE = new MyBigInteger("3");

    private int[] digits;
    private int sign;

    public MyBigInteger(String str) {
        if (str.charAt(0) == '-') {
            sign = -1;
            str = str.substring(1);
        } else {
            sign = 1;
        }
        digits = new int[str.length()];
        for (int i = 0; i < str.length(); i++) {
            digits[str.length() - 1 - i] = str.charAt(i) - '0';
        }
    }

    public MyBigInteger(int[] digits, int sign) {
        this.digits = digits;
        this.sign = sign;
    }

    public MyBigInteger(int sign, int[] digits) {
        this.digits = digits;
        this.sign = sign;
    }

    private int[] add(int[] x, int[] y) {
        int[] z = new int[Math.max(x.length, y.length) + 1];
        int carry = 0;
        for (int i = 0; i < z.length; i++) {
            int xi = i < x.length ? x[i] : 0;
            int yi = i < y.length ? y[i] : 0;
            long sum = ((long) xi & 0xffffffffL) + ((long) yi & 0xffffffffL) + carry;
            z[i] = (int) sum;
            carry = (int) (sum >>> 32);
        }
        removeLeadingZeros(z);
        return z;
    }

    public MyBigInteger subtract(MyBigInteger other) {
        int[] resultDigits = new int[Math.max(digits.length, other.digits.length)];
        int borrow = 0;
        for (int i = 0; i < resultDigits.length; i++) {
            int diff = borrow;
            if (i < digits.length) {
                diff += digits[i];
            }
            if (i < other.digits.length) {
                diff -= other.digits[i];
            }
            if (diff < 0) {
                borrow = -1;
                diff += 10;
            } else {
                borrow = 0;
            }
            resultDigits[i] = diff;
        }
        removeLeadingZeros(resultDigits);
        return new MyBigInteger(resultDigits, sign * other.sign);
    }

    public MyBigInteger multiply(MyBigInteger other) {
        int[] resultDigits = new int[digits.length + other.digits.length];
        for (int i = 0; i < digits.length; i++) {
            int carry = 0;
            for (int j = 0; j < other.digits.length; j++) {
                int product = carry + resultDigits[i + j] + digits[i] * other.digits[j];
                resultDigits[i + j] = product % 10;
                carry = product / 10;
            }
            resultDigits[i + other.digits.length] += carry;
        }
        removeLeadingZeros(resultDigits);
        return new MyBigInteger(resultDigits, sign * other.sign);
    }

    public MyBigInteger divide(MyBigInteger other) {
        if (other.signum() == 0) {
            throw new ArithmeticException("Division by zero");
        }
        if (signum() == 0) {
            return new MyBigInteger(digits, 0);
        }
        MyBigInteger dividend = this.abs();
        MyBigInteger divisor = other.abs();
        MyBigInteger quotient = new MyBigInteger("0");
        MyBigInteger remainder = new MyBigInteger("0");
        for (int i = digits.length - 1; i >= 0; i--) {
            remainder = remainder.multiply(new MyBigInteger("10"));
            remainder = remainder.add(new MyBigInteger(Integer.toString(digits[i])));
            while (remainder.compareTo(divisor) >= 0) {
                remainder = remainder.subtract(divisor);
                quotient.digits[i]++;
            }
        }
        quotient.removeLeadingZeros();
        if (signum() != other.signum()) {
            quotient = quotient.negate();
        }
        return quotient;
    }

    public MyBigInteger abs() {
        return signum() >= 0 ? this : new MyBigInteger(digits, 1);
    }

    private String toDecimalString() {
        StringBuilder sb = new StringBuilder();
        if (signum() < 0) {
            sb.append('-');
        }
        for (int i = digits.length - 1; i >= 0; i--) {
            sb.append(digits[i]);
        }
        return sb.toString();
    }

    public MyBigInteger mod(MyBigInteger other) {
        if (other.signum() == 0) {
            throw new ArithmeticException("Division by zero");
        }
        if (signum() == 0) {
            return new MyBigInteger(digits, 0);
        }
        MyBigInteger dividend = this.abs();
        MyBigInteger divisor = other.abs();
        MyBigInteger quotient = dividend.divide(divisor);
        MyBigInteger remainder = dividend.subtract(quotient.multiply(divisor));
        return remainder.multiply(new MyBigInteger(Integer.toString(signum())));
    }
    public MyBigInteger shiftLeft(int n) {
        if (sign == 0 || n == 0) {
            return this;
        }

        int intShift = n / 32;
        int bitShift = n % 32;
        int[] resultDigits = new int[digits.length + intShift + (bitShift == 0 ? 0 : 1)];
        int hiBits = 0;
        for (int i = 0; i < digits.length; i++) {
            int shifted = (digits[i] << bitShift) | hiBits;
            resultDigits[i + intShift] = shifted;
            hiBits = digits[i] >>> (32 - bitShift);
        }
        if (hiBits != 0) {
            resultDigits[resultDigits.length - 1] = hiBits;
        }
        return new MyBigInteger(sign, resultDigits);
    }

    public static MyBigInteger valueOf(int[] digits, int offset, int length) {
        int i = offset + length - 1;
        while (i >= offset && digits[i] == 0) {
            i--;
        }
        if (i < offset) {
            return ZERO;
        }
        int[] resultDigits = new int[i - offset + 1];
        for (int j = 0; j < resultDigits.length; j++) {
            resultDigits[j] = digits[i - j];
        }
        return new MyBigInteger(1, resultDigits);
    }

    public MyBigInteger shiftRight(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be non-negative");
        }
        if (n == 0 || sign == 0) {
            return this;
        }
        int[] result = new int[digits.length];
        int offset = n / 32;
        int shift = n % 32;
        int lowBits = 0;
        for (int i = 0; i < digits.length - offset; i++) {
            lowBits = digits[i + offset] >>> shift;
            if (i > 0) {
                lowBits |= (digits[i + offset - 1] << (32 - shift));
            }
            result[i] = lowBits;
        }
        return new MyBigInteger(sign, result);
    }

    public MyBigInteger shiftRight() {
        int[] resultDigits = new int[digits.length - 1];
        System.arraycopy(digits, 1, resultDigits, 0, digits.length - 1);
        removeLeadingZeros(resultDigits);
        return new MyBigInteger(resultDigits, sign);
    }

    public boolean isProbablePrime(int certainty) {
        if (compareTo(TWO) < 0) {
            return compareTo(TWO.negate()) > 0;
        }
        if (testSmallPrimes()) {
            return true;
        }
        MyBigInteger minusOne = subtract(ONE);
        int s = 0;
        MyBigInteger d = minusOne;
        while (d.mod(TWO).equals(ZERO)) {
            s++;
            d = d.divide(TWO);
        }
        Random random = new Random();
        for (int i = 0; i < certainty; i++) {
            MyBigInteger a = new MyBigInteger(digits, 0);
            do {
                for (int j = 0; j < digits.length; j++) {
                    a.digits[j] = random.nextInt(10);
                }
            } while (a.compareTo(ONE) <= 0 || a.compareTo(minusOne) >= 0);
            MyBigInteger x = a.modPow(d, this);
            if (x.equals(ONE) || x.equals(minusOne)) {
                continue;
            }
            boolean found = false;
            for (int r = 0; r < s; r++) {
                x = x.modPow(TWO, this);
                if (x.equals(minusOne)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                return false;
            }
        }
        return true;
    }
//    public static MyBigInteger probablePrime(int bitLength, Random rnd) {
//        if (bitLength < 2) {
//            throw new IllegalArgumentException("bitLength must be at least 2");
//        }
//
//        MyBigInteger prime;
//        while (true) {
//            prime = MyBigInteger.probablePrime(bitLength, rnd);
//            if (MyBigInteger(prime)) {
//                return prime;
//            }
//        }
//    }

    public boolean isProbablePrime(MyBigInteger n) {
        if (n.compareTo(MyBigInteger.ONE) <= 0 || !n.testBit(0)) {
            return false;
        }
        MyBigInteger two = MyBigInteger.valueOf(2);
        if (n.equals(two)) {
            return true;
        }
        MyBigInteger d = n.subtract(MyBigInteger.ONE);
        int s = d.getLowestSetBit();
        d = d.shiftRight(s);
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for (int i = 0; i < primes.length; i++) {
            MyBigInteger a = MyBigInteger.valueOf(primes[i]);
            if (a.compareTo(n) >= 0) {
                break;
            }
            MyBigInteger x = a.modPow(d, n);
            if (x.equals(MyBigInteger.ONE) || x.equals(n.subtract(MyBigInteger.ONE))) {
                continue;
            }
            boolean isComposite = true;
            for (int j = 0; j < s - 1; j++) {
                x = x.modPow(two, n);
                if (x.equals(MyBigInteger.ONE)) {
                    return false;
                }
                if (x.equals(n.subtract(MyBigInteger.ONE))) {
                    isComposite = false;
                    break;
                }
            }
            if (isComposite && !x.equals(n.subtract(MyBigInteger.ONE))) {
                return false;
            }
        }
        return true;
    }

    public static MyBigInteger valueOf(long val) {
        if (val == 0) {
            return ZERO;
        }
        int signum = val > 0 ? 1 : -1;
        val *= signum;
        int length = 0;
        long temp = val;
        while (temp != 0) {
            length++;
            temp >>>= 32;
        }
        int[] digits = new int[length];
        for (int i = 0; i < digits.length; i++) {
            digits[i] = (int) val;
            val >>>= 32;
        }
        return new MyBigInteger(signum, digits);
    }

    public int getLowestSetBit() {
        if (sign == 0) {
            return -1;
        }
        int i = 0;
        while (digits[i] == 0) {
            i++;
        }
        int j = 0;
        while ((digits[i] & (1 << j)) == 0) {
            j++;
        }
        return 32*i + j;
    }

    private boolean testSmallPrimes() {
        for (int prime : SMALL_PRIMES) {
            if (mod(new MyBigInteger(Integer.toString(prime))).equals(ZERO)) {
                return false;
            }
        }
        return true;
    }

    public MyBigInteger modPow(MyBigInteger exponent, MyBigInteger modulus) {
        if (modulus.signum() <= 0) {
            throw new ArithmeticException("Modulus must be positive");
        }
        if (exponent.signum() < 0) {
            throw new ArithmeticException("Exponent must be nonnegative");
        }
        if (modulus.equals(ONE)) {
            return ZERO;
        }
        MyBigInteger result = ONE;
        MyBigInteger base = this.mod(modulus);
        while (exponent.signum() > 0) {
            if (exponent.mod(TWO).equals(ONE)) {
                result = result.multiply(base).mod(modulus);
            }
            exponent = exponent.shiftRight(1);
            base = base.multiply(base).mod(modulus);
        }
        return result;
    }

    public int signum() {
        return Integer.signum(sign);
    }

    public MyBigInteger negate() {
        return new MyBigInteger(digits, -sign);
    }

    public int compareTo(MyBigInteger other) {
        if (sign != other.sign) {
            return signum() - other.signum();
        }
        if (digits.length != other.digits.length) {
            return sign * (digits.length - other.digits.length);
        }
        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] != other.digits[i]) {
                return sign * (digits[i] - other.digits[i]);
            }
        }
        return 0;
    }

    public static MyBigInteger probablePrime(int bitLength, Random rnd) {
        // 确保位长度不小于 2
        if (bitLength < 2) {
            throw new IllegalArgumentException("Bit length too small: " + bitLength);
        }
        // 生成一个随机的大整数作为候选素数
        MyBigInteger candidate = new MyBigInteger(bitLength, rnd);
        // 通过试除法检查候选素数是否为质数
        while (!candidate.isProbablePrime()) {
            // 如果候选素数不是质数，则将其增加 2，并重新检查
            candidate = candidate.add(TWO);
        }
        return candidate;
    }

    private MyBigInteger(int bitLength, Random rnd) {
        digits = new int[(bitLength + 31) / 32];
        for (int i = 0; i < digits.length; i++) {
            digits[i] = rnd.nextInt();
        }
        // 将最高位的符号位设为 0，以确保生成的整数为非负数
        digits[digits.length - 1] &= 0x7fffffff;
        // 去除多余的位，以使整数的位长度为 bitLength
        int excessBits = 32 * digits.length - bitLength;
        if (excessBits > 0) {
            digits[digits.length - 1] >>>= excessBits;
        }
        // 去除前导的 0，以使整数的位长度为 bitLength
        removeLeadingZeros(digits);
        // 如果生成的整数为 0，则将其增加 1，以确保其不为偶数
        if (digits.length == 1 && digits[0] == 0) {
            digits[0] = 1;
        }
        sign = 1;
    }

    public boolean testBit(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("Negative bit position");
        }
        int digitIndex = n / 32;
        if (digitIndex >= digits.length) {
            return false;
        }
        int bitIndex = n % 32;
        return (digits[digitIndex] & (1 << bitIndex)) != 0;
    }

    public int bitLength() {
        int n = digits.length;
        int leadingZeros = Integer.numberOfLeadingZeros(digits[n - 1]);
        return 32 * (n - 1) + (32 - leadingZeros);
    }

    private boolean isProbablePrime() {
        // 如果整数不是奇数，则不是质数
        if (testBit(0) == false) {
            return false;
        }
        // 如果整数小于等于 97，则可以通过试除法检查其是否为质数
        if (compareTo(new MyBigInteger(Integer.toString(97))) <= 0) {
            for (int prime : SMALL_PRIMES) {
                if (mod(new MyBigInteger(Integer.toString(prime))).equals(ZERO)) {
                    return false;
                }
            }
            return true;
        }
        // 使用米勒-拉宾素性检验判断整数是否为质数
        int s = 0;
        MyBigInteger d = subtract(ONE);
        while (d.testBit(0) == false) {
            s++;
            d = d.shiftRight(1);
        }
        for (int i = 0; i < 100; i++) {
            MyBigInteger a = new MyBigInteger(bitLength(), new Random());
            MyBigInteger x = a.modPow(d, this);
            if (x.equals(ONE) == false && x.equals(subtract(ONE)) == false) {
                for (int j = 1; j < s; j++) {
                    x = x.modPow(TWO, this);
                    if (x.equals(subtract(ONE))) {
                        break;
                    }
                    if (x.equals(ONE)) {
                        return false;
                    }
                }
                if (x.equals(subtract(ONE)) == false) {
                    return false;
                }
            }
        }
        return true;
    }

    private boolean equals(int[] a, int[] b) {
        if (a.length != b.length) {
            return false;
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return false;
            }
        }
        return true;
    }

    public MyBigInteger and(MyBigInteger val) {
        int[] resultDigits = new int[Math.min(digits.length, val.digits.length)];
        for (int i = 0; i < resultDigits.length; i++) {
            resultDigits[i] = digits[i] & val.digits[i];
        }
        removeLeadingZeros(resultDigits);
        return new MyBigInteger(sign, resultDigits);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        if (sign < 0) {
            sb.append("-");
        }
        for (int i = digits.length - 1; i >= 0; i--) {
            sb.append(digits[i]);
        }
        return sb.toString();
    }

    private void removeLeadingZeros() {
        removeLeadingZeros(digits);
    }

    private void removeLeadingZeros(int[] digits) {
        int i = digits.length - 1;
        while (i > 0 && digits[i] == 0) {
            i--;
        }
        if (i < digits.length - 1) {
            int[] copy = new int[i + 1];
            System.arraycopy(digits, 0, copy, 0, i + 1);
            this.digits = copy;
        }
    }

    public byte byteValue() {
        return (byte) digits[0];
    }

    public byte[] toByteArray() {
        int bitLength = bitLength();
        int byteLength = (bitLength + 7) / 8;
        byte[] byteArray = new byte[byteLength];
        int bitOffset = 0;
        for (int i = 0; i < byteLength; i++) {
            int bitIndex = bitOffset % 32;
            int digitIndex = bitOffset / 32;
            int bitsNeeded = Math.min(8 - bitIndex, 32 - bitIndex);
            int bitsFromDigit = Math.min(bitsNeeded, bitLength - bitOffset);
            int shift = 24 + bitIndex;
            int mask = (0xff << shift) >>> shift;
            byteArray[i] = (byte) ((digits[digitIndex] & mask) >>> (24 + bitIndex - bitsFromDigit + 1));
            bitOffset += bitsFromDigit;
        }
        return byteArray;
    }

    public MyBigInteger add(MyBigInteger other) {
        if (sign == other.sign) {
            int[] resultDigits = add(digits, other.digits);
            return new MyBigInteger(resultDigits, sign);
        } else if (sign == -1) {
            return other.subtract(new MyBigInteger(digits, 1));
        } else {
            return subtract(new MyBigInteger(other.digits, 1));
        }
    }

    public MyBigInteger(int signum, byte[] magnitude) {
        if (magnitude.length == 0) {
            digits = new int[1];
            sign = 0;
            return;
        }
        boolean leadingZero = (magnitude[0] & 0x80) == 0x80;
        int length = leadingZero ? magnitude.length + 1 : magnitude.length;
        digits = new int[(length + 3) / 4];
        for (int i = 0; i < magnitude.length; i++) {
            int digitIndex = (length - i - 1) / 4;
            int digitOffset = (length - i - 1) % 4;
            digits[digitIndex] |= (magnitude[i] & 0xff) << (8 * digitOffset);
        }
        if (leadingZero) {
            digits[digits.length - 1] |= 0x80000000;
        }
        removeLeadingZeros(digits);
        sign = digits.length == 1 && digits[0] == 0 ? 0 : signum;
    }
}

